package linked;

import java.util.ListIterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Ex148 {
    //选择排序：超时
    static class Solution {
        public ListNode sortList1(ListNode head) {
            if (head == null || head.next == null) return head;
           ListNode minPre, cur = head, res = new ListNode(0), result = res;
        //    head = null;
           while (head.next != null) {
              minPre = findMinPre(head);
              if (minPre.val == Integer.MIN_VALUE) {
                  //当头结点为最小值
                  res.next = head;
                  head = head.next;
              } else {
                  //其他节点为最小值
                  res.next = minPre.next;
                  minPre.next = minPre.next.next;
              }
              System.out.println(head);
              res = res.next;
           }
            res.next = head;
            return result.next;
        }

        public ListNode findMinPre(ListNode head) {
            ListNode cur = head, min = head, pre = null;
            while (cur.next != null) {
                if (cur.next.val < min.val) {
                    pre = cur;
                    min = cur.next;
                }
                cur = cur.next;
            }
            if (pre == null) return new ListNode(Integer.MIN_VALUE);
            return pre;
        }

        //API堆排序，不符合空间要求
        public ListNode sortList2(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode res = new ListNode(0), result = res, cur = head;
            Queue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
            while (cur != null) {
                queue.offer(cur);
                cur = cur.next;
            }
            while (!queue.isEmpty()) {
                res.next = queue.poll();
                res = res.next;
            }
            return result.next;
        }

        //递归的归并排序，不符合空间要求【空间复杂度O(logN)，数组下的递归法是O(n)，是因为需要额外的一个数组；而链表只需要修改节点指针即可
        //每次划分一半区域，最终划分到1个时，消耗log2(n)的递归深度，一趟递归只会使用一路的结果，之后就会出栈】
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode fast = head, slow = head, left, right, mid = slow; 

            //使用快慢指针，找到链表中点
            while (fast != null && fast.next != null) {
                fast = fast.next.next;

                //这样可以让划分平均一点
                mid = slow;
                slow = slow.next;
            }
            
            //分开两个链表
          /*   mid = slow.next;
            slow.next = null; */
            mid.next = null;

            System.out.println(head + "=============" + slow);
        
            //得到后面归并好的链表
            left = sortList(head);
            right = sortList(slow);
            //归并两个有序链表
            return merge(left, right);
        }
        public ListNode merge(ListNode p, ListNode q) {
            ListNode res = new ListNode(0), result = res;
            while (p != null && q != null) {
                if (p.val <= q.val) {
                    res.next = p;
                    p = p.next;
                } else {
                    res.next = q;
                    q = q.next;
                }
                res = res.next;
            }
            if (p == null) {
                p = q;
            }
            res.next = p;
            return result.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode head = new ListNode(0);
        ListNode cur = head;
        cur.next = new ListNode(-1);
        cur = cur.next;
        cur.next = new ListNode(-2);
        cur  = cur.next;
        cur.next = new ListNode(10);
        ListNode res = solution.findMinPre(head);

        res = solution.sortList(head);
        System.out.println(res);

    }
}
